package com.sicheng.lc.杂题.栈;

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Map;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/13 17:51
 */
public class 最大频率栈 {

    //https://leetcode.cn/problems/maximum-frequency-stack/
    // 遇到频次的 首先套路是有一个缓存 用于缓存元素的 关键信息
    // 还有一个频次的缓存 缓存某个频次的一批元素
    static class FreqStack {

        // 记录最大频率
        private int max;
        // 记录每个元素的频率
        private final Map<Integer, Integer> cache = new HashMap<>();
        // 记录某一频率的所有元素
        private final Map<Integer, ArrayDeque<Integer>> freCache = new HashMap<>();

        public FreqStack() {
        }

        public void push(int val) {
            int x = cache.getOrDefault(val, 0);
            cache.put(val, x + 1);
            if (x + 1 > max)
                max = x + 1;
            ArrayDeque<Integer> stack = freCache.computeIfAbsent(x + 1, k -> new ArrayDeque<>(16));
            stack.push(val);
        }

        public int pop() {
            ArrayDeque<Integer> stack = freCache.get(max);
            int top = stack.pop();
            if (stack.isEmpty())
                max--;
            cache.put(top, cache.get(top) - 1);
            return top;
        }
    }
}
